package demo;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Solution {

        //非递归写法
        public List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> list = new ArrayList<>();
            TreeNode cur = root;
            Deque<TreeNode> stack = new LinkedList<>();
            //last用来标记已经出栈的元素
            TreeNode last = null;
            //当cur不为空和stack不为空时进入循环
            while (cur != null || !stack.isEmpty()) {
                //先把所有左子树最左的放入栈中
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                //查看栈顶元素
                TreeNode top = stack.peek();
                //如果栈顶元素的右孩子为空（因为栈里结点的元素都是左孩子了，所有没有左孩子）
                //直接出栈
                if (top.right == null) {
                    top = stack.pop();
                    list.add(top.val);
                    last = top;
                    //如果有右孩子但右孩子是已经处理的 也直接出栈
                } else if (top.right == last) {
                    top = stack.pop();
                    list.add(top.val);
                    last = top;
                } else {
                    //有右孩子但未处理往右走
                    cur = top.right;
                }
            }
            return list;
        }
}
